Educational Codeforces Round 109 (Div. 2) B Permutation Sort
区間[$ 1, n - 1]と[$ 2, n]にのみ操作を適用するとしても答えは変化しないことに注目する.
よって, 次のように場合分けすればよい.
与えられた数列がすでに順列である場合
この場合, 操作の必要はない.
$ a_1 = n, a_n = 1の場合
この場合, 左端と右端を入れ替えなければならず, 実験してみると3回の操作で実現できることがわかる.
これら以外で, $ a_1 = 1もしくは$ a_n = nの場合(左端と右端の少なくとも一方について操作の必要がない場合)
この場合, [$ 1, n - 1]と[$ 2, n]の操作の片方しか必要ない. よって必要な操作回数は1回となる.
これら以外の場合(両方操作の必要がある場合)
この場合, [$ 1, n - 1]と[ $ 2, n]の操作についてそれぞれ1回ずつ操作することにより実現できる. よって必要な操作回数は2回となる.
よってこの問題を適切な場合分けにより$ O(n)で解くことができた.